import random
from collections import defaultdict

import matplotlib.pyplot as plt
import numpy as np
import heapq

radius = 10


def gen_points(center_x, center_y, n_points, radius=10):
    # Generate random points inside the circle
    res = []
    while len(res) < n_points:
        x = round(np.random.uniform(center_x - radius, center_x + radius), 5)
        y = round(np.random.uniform(center_y - radius, center_y + radius), 5)
        if (x - center_x) ** 2 + (y - center_y) ** 2 <= radius ** 2:
            res.append((x, y))
    return res


def prim_mst(graph):
    """
    实现Prim算法求解最小生成树

    # 示例图（用邻接表表示）
    graph = {
        'A': [('B', 1), ('C', 4)],
        'B': [('A', 1), ('C', 2), ('D', 5)],
        'C': [('A', 4), ('B', 2), ('D', 1)],
        'D': [('B', 5), ('C', 1)]
    }

    :param graph: 用邻接表表示的图，graph[u] 是一个列表，包含(u, v, weight)形式的边
    :return: 最小生成树的总权重和边列表
    """
    if not graph:
        return 0, []

    start_vertex = list(graph.keys())[0]
    visited = set()
    min_heap = [(0, start_vertex, None)]  # (权重, 顶点, 前驱顶点)
    mst_weight = 0
    mst_edges = []

    while min_heap:
        weight, u, prev = heapq.heappop(min_heap)
        if u in visited:
            continue

        visited.add(u)
        mst_weight += weight
        if prev is not None:
            mst_edges.append((prev, u, weight))

        for v, w in graph[u]:
            if v not in visited:
                heapq.heappush(min_heap, (w, v, u))

    return mst_edges


def build_mst_graph(mst_edges):
    """
    根据最小生成树的边构建邻接表表示的图

    :param mst_edges: 最小生成树的边列表
    :return: 邻接表表示的图
    """
    mst_graph = defaultdict(list)
    for u, v, weight in mst_edges:
        mst_graph[u].append((v, weight))
        mst_graph[v].append((u, weight))
    return mst_graph


def preorder_traversal(graph, start):
    """
    对图进行先序遍历

    :param graph: 邻接表表示的图
    :param start: 起始顶点
    :return: 先序遍历的顶点顺序
    """
    visited = set()
    traversal_order = []

    def dfs(v):
        visited.add(v)
        traversal_order.append(v)
        for neighbor, _ in graph[v]:
            if neighbor not in visited:
                dfs(neighbor)

    dfs(start)
    return traversal_order


if __name__ == '__main__':

    # Set the size of the plot
    plt.figure()

    colors = ['red', 'blue', 'green', 'purple', 'orange']

    centers = [
        [random.randint(10, 20), random.randint(10, 20)],
        [random.randint(10, 20), random.randint(20, 30)],
        [random.randint(20, 30), random.randint(10, 30)],
        [random.randint(20, 30), random.randint(20, 30)],
        [random.randint(15, 25), random.randint(15, 25)],
    ]

    for i in range(5):
        # Circle parameters
        center_x, center_y = centers[i]
        points = gen_points(center_x, center_y, 25)

        # Extract x and y coordinates of points
        x_points, y_points = zip(*points)
        print(x_points, y_points)

        # Plot the circle with blue outline
        circle = plt.Circle((center_x, center_y), radius, edgecolor=colors[i], facecolor='none')
        plt.gca().add_patch(circle)

        # Plot the points
        plt.scatter(x_points, y_points, color=colors[i])

        # Plot the center point
        plt.scatter(center_x, center_y, color='black')

    # Set the limits and aspect ratio of the plot
    plt.xlim(0, 40)
    plt.ylim(0, 40)
    plt.gca().set_aspect('equal', adjustable='box')

    # Add grid to the background
    plt.grid(True)

    # Show the plot
    plt.show()
